{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split Linked List in Parts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: splitListToParts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分隔链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个头结点为 <code>head</code> 的单链表和一个整数 <code>k</code> ，请你设计一个算法将链表分隔为 <code>k</code> 个连续的部分。</p>\n",
    "\n",
    "<p>每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。</p>\n",
    "\n",
    "<p>这 <code>k</code> 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。</p>\n",
    "\n",
    "<p>返回一个由上述 <code>k</code> 部分组成的数组。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/13/split1-lc.jpg\" style=\"width: 400px; height: 134px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3], k = 5\n",
    "<strong>输出：</strong>[[1],[2],[3],[],[]]\n",
    "<strong>解释：</strong>\n",
    "第一个元素 output[0] 为 output[0].val = 1 ，output[0].next = null 。\n",
    "最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 [] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/13/split2-lc.jpg\" style=\"width: 600px; height: 60px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5,6,7,8,9,10], k = 3\n",
    "<strong>输出：</strong>[[1,2,3,4],[5,6,7],[8,9,10]]\n",
    "<strong>解释：</strong>\n",
    "输入被分成了几个连续的部分，并且每部分的长度相差不超过 1 。前面部分的长度大于等于后面部分的长度。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目在范围 <code>[0, 1000]</code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-linked-list-in-parts](https://leetcode.cn/problems/split-linked-list-in-parts/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-linked-list-in-parts](https://leetcode.cn/problems/split-linked-list-in-parts/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n5', '[1,2,3,4,5,6,7,8,9,10]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        ans=[None]*k\n",
    "        cnt=0\n",
    "        p=head\n",
    "        while p!=None:\n",
    "            p=p.next\n",
    "            cnt+=1\n",
    "        for i in range(k):\n",
    "            size=math.ceil(cnt/(k-i))\n",
    "            cnt-=size\n",
    "            if size==0:\n",
    "                break\n",
    "            p=head\n",
    "            for _ in range(size-1):\n",
    "                p=p.next\n",
    "            tmp=p.next\n",
    "            p.next=None\n",
    "            ans[i]=head\n",
    "            head=tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:\n",
    "        dummp = ListNode()\n",
    "        dummp.next = head\n",
    "\n",
    "        def get_len(node, n):\n",
    "            if not node:\n",
    "                return n\n",
    "            return get_len(node.next, n + 1)\n",
    "            \n",
    "        n = get_len(dummp.next, 0)\n",
    "        num, extra = n // k, n % k\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            if n > 0:\n",
    "                son_len = num if extra <= 0 else num + 1\n",
    "                extra -= 1\n",
    "                cur, temp = ListNode(), ListNode()\n",
    "                cur.next = head\n",
    "                while son_len > 1 and head:\n",
    "                    head = head.next\n",
    "                    son_len -= 1\n",
    "                if head:\n",
    "                    temp.next = head.next\n",
    "                    head.next = None\n",
    "                head = temp.next\n",
    "                ans.append(cur.next)\n",
    "            else:\n",
    "                ans.append(None)\n",
    "            n -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:\n",
    "        n = 0\n",
    "        head1 = head\n",
    "        while head1:\n",
    "            head1 = head1.next\n",
    "            n+=1\n",
    "        s = n%k\n",
    "        l = n//k\n",
    "        res_len = [1]*s + [0]*(k-s)\n",
    "        res_len = [_+l for _ in res_len]\n",
    "        head2=head\n",
    "        res = []\n",
    "        print (res_len)\n",
    "        for r in res_len:\n",
    "            # print (r,111)\n",
    "            if r==0:\n",
    "                tmp2 = None\n",
    "            else:\n",
    "                print (1111,res)\n",
    "                tmp = ListNode(head2.val)\n",
    "                head2=head2.next\n",
    "                r -= 1\n",
    "                tmp2=tmp\n",
    "                while r>0:\n",
    "                    r-=1\n",
    "                    tmp.next = ListNode(head2.val)\n",
    "                    head2=head2.next\n",
    "                    \n",
    "                    tmp = tmp.next\n",
    "            # print (4444,tmp2,head2)\n",
    "            res.append(tmp2)\n",
    "        return res\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:\n",
    "        '''\n",
    "        n = 0\n",
    "        node = head\n",
    "        while node:\n",
    "            node = node.next\n",
    "            n += 1\n",
    "        res = [None]*k\n",
    "        if n <= k:\n",
    "            for i in range(k):\n",
    "                res[i] = head\n",
    "                if head:\n",
    "                    head = head.next\n",
    "                else:\n",
    "                    break\n",
    "                res[i].next = None\n",
    "            return res\n",
    "        num,over = n//k,n%k\n",
    "        cur = head\n",
    "        for i in range(k):\n",
    "            res[i] = cur\n",
    "            pre = ListNode(0,cur)\n",
    "            if over > 0:\n",
    "                for _ in range(num+1):\n",
    "                    pre = pre.next\n",
    "                over -= 1\n",
    "            else:\n",
    "                for _ in range(num):\n",
    "                    pre = pre.next          \n",
    "            cur = pre.next\n",
    "            pre.next = None           \n",
    "        return res\n",
    "        '''\n",
    "\n",
    "        def cal(head:ListNode):\n",
    "            if not head:\n",
    "                return 0\n",
    "            return cal(head.next)+1\n",
    "        n = cal(head)\n",
    "        res = [None for _ in range(k)]\n",
    "        if n <= k:\n",
    "            cur = head\n",
    "            for i in range(k):\n",
    "                if cur:\n",
    "                    res[i] = cur\n",
    "                else:\n",
    "                    break\n",
    "                cur = cur.next\n",
    "                res[i].next = None\n",
    "\n",
    "        else:\n",
    "            num,over = n//k,n%k\n",
    "            cur = head\n",
    "            for i in range(over):\n",
    "                res[i] = cur\n",
    "                pre = ListNode(0,cur)\n",
    "                for _ in range(num+1):                    \n",
    "                    pre = pre.next\n",
    "                cur = pre.next\n",
    "                pre.next = None\n",
    "            for i in range(over,k):\n",
    "                res[i] = cur\n",
    "                pre = ListNode(0,cur)\n",
    "                for _ in range(num):                    \n",
    "                    pre = pre.next\n",
    "                cur = pre.next\n",
    "                pre.next = None\n",
    "                \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        count=0\n",
    "        stack=[]\n",
    "        while head:\n",
    "            stack.append(head)\n",
    "            count+=1\n",
    "            head=head.next\n",
    "        while count<k:\n",
    "            count+=1\n",
    "            stack.append(None)\n",
    "        percount=[count//k]*k\n",
    "        lef=count%k\n",
    "        for j in range(lef):\n",
    "            percount[j]+=1\n",
    "        out=[]\n",
    "        nowid=0\n",
    "        for j in percount:\n",
    "            if stack[nowid+j-1]:\n",
    "                stack[nowid+j-1].next=None\n",
    "            out.append(stack[nowid])\n",
    "            nowid+=j\n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        length=0\n",
    "        cur=head\n",
    "        while cur:\n",
    "            length+=1\n",
    "            cur=cur.next\n",
    "\n",
    "        count=length//k \n",
    "        left=length%k\n",
    "        \n",
    "        pre,cur=None,head\n",
    "        res=[]\n",
    "        for _ in range(k):\n",
    "            res.append(cur)\n",
    "            temp=count+1 if left>0 else count\n",
    "            if cur:\n",
    "                for i in range(temp-1):\n",
    "                    cur=cur.next\n",
    "                nxt=cur.next\n",
    "                cur.next=None\n",
    "                cur=nxt\n",
    "                left-=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        cur = head\n",
    "        n = 0\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            n += 1\n",
    "        a, b = divmod(n, k)\n",
    "        cur = head\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            head = cur\n",
    "            for _ in range(a + int(b > 0) - 1):\n",
    "                cur = cur.next\n",
    "            b -= 1\n",
    "            res.append(head)\n",
    "            if cur:\n",
    "                t = cur.next\n",
    "                cur.next = None\n",
    "                cur = t\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        cur, l = head, 0\n",
    "        while cur:\n",
    "            l += 1\n",
    "            cur = cur.next\n",
    "        each, mod = l // k, l % k\n",
    "        cur, ans, idx = head, [None] * k, 0\n",
    "        while cur:\n",
    "            ans[idx] = cur\n",
    "            last = None\n",
    "            for i in range(each + (idx < mod)):\n",
    "                last = cur\n",
    "                cur = cur.next\n",
    "            idx += 1\n",
    "            last.next = None\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:\n",
    "        n = 0\n",
    "        node = head\n",
    "        while node:\n",
    "            n += 1\n",
    "            node = node.next\n",
    "        quotient, remainder = n // k, n % k\n",
    "\n",
    "        parts = [None for _ in range(k)]\n",
    "        i, curr = 0, head\n",
    "        while i < k and curr:\n",
    "            parts[i] = curr\n",
    "            part_size = quotient + (1 if i < remainder else 0)\n",
    "            for _ in range(part_size - 1):\n",
    "                curr = curr.next\n",
    "            next = curr.next\n",
    "            curr.next = None\n",
    "            curr = next\n",
    "            i += 1\n",
    "        return parts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        n_total = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            n_total += 1\n",
    "            \n",
    "        ## 每一段 分几个 ##\n",
    "        n_part = n_total // k\n",
    "        ## 剩下几个，够前几段分 ##\n",
    "        n_left = n_total - n_part * k\n",
    "\n",
    "        \n",
    "        res = []\n",
    "        cur = head\n",
    "        \n",
    "        for i in range(k):\n",
    "            n_part2 = n_part\n",
    "            if i < n_left:\n",
    "                n_part2 += 1\n",
    "            \n",
    "            head_i = tmp = ListNode()\n",
    "            for j in range(n_part2):\n",
    "                tmp.next = cur\n",
    "                cur = cur.next\n",
    "                tmp = tmp.next\n",
    "            tmp.next = None\n",
    "            res.append(head_i.next)\n",
    "            # print_nodelist(res[-1])\n",
    "        \n",
    "        return(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        length = 0\n",
    "        q = p = head\n",
    "        while p:\n",
    "            p=p.next\n",
    "            length+=1\n",
    "        gs = length // k\n",
    "        lg = length % k\n",
    "        gl = [gs]*k\n",
    "        for i in range(lg):\n",
    "            gl[i]+=1\n",
    "        res = [[]]*k\n",
    "        for i in range(k):\n",
    "            l = gl[i]\n",
    "            dummy=t= ListNode(0,q)\n",
    "            while q and l>0:\n",
    "                q = q.next\n",
    "                t= t.next\n",
    "                l-=1\n",
    "            t.next= None\n",
    "            res[i] = dummy.next\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        cnt = 0\n",
    "        node = head\n",
    "        while node:\n",
    "            cnt += 1\n",
    "            node = node.next\n",
    "        avg, rem = divmod(cnt, k)\n",
    "        node = head\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            tmp = cur = ListNode()\n",
    "            if i < rem: val = avg + 1\n",
    "            else: val = avg\n",
    "            for _ in range(val):\n",
    "                cur.next = node\n",
    "                node, cur = node.next, cur.next\n",
    "            if cur: cur.next = None\n",
    "            ans.append(tmp.next)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\r\n",
    "        if not head:\r\n",
    "            return [None]*k\r\n",
    "        cur=head\r\n",
    "        cnt=0\r\n",
    "        while cur:\r\n",
    "            cnt+=1\r\n",
    "            cur=cur.next\r\n",
    "        avg=cnt//k\r\n",
    "        remaning=cnt%k\r\n",
    "        ret=[]\r\n",
    "        cur=head\r\n",
    "        for i in range(k):\r\n",
    "            ret.append(cur)\r\n",
    "            if not cur:\r\n",
    "                continue\r\n",
    "            length=avg\r\n",
    "            if remaning:\r\n",
    "                length+=1\r\n",
    "                remaning-=1\r\n",
    "            for _ in range(length-1):\r\n",
    "                cur=cur.next\r\n",
    "            if not cur:\r\n",
    "                continue\r\n",
    "            temp=cur.next\r\n",
    "            cur.next=None\r\n",
    "            cur=temp\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        # 读取一下链表长度\n",
    "        length = 0\n",
    "        current = head # 指针 \n",
    "        while current:\n",
    "            length += 1\n",
    "            current = current.next\n",
    "        \n",
    "        # 确定 各个 part的长度\n",
    "        wid, extra = divmod(length, k)\n",
    "\n",
    "        # 分割链表\n",
    "        current = head\n",
    "        result =  []\n",
    "        for i in range(k):\n",
    "            part_head = current\n",
    "            # 当前部分如果需要额外的node，就减少一个额外值\n",
    "            for j in range(wid + (i < extra) - 1):\n",
    "                if current:\n",
    "                    current = current.next\n",
    "            if current:\n",
    "                current.next, current = None, current.next # 给下一个做初始化\n",
    "            result.append(part_head)    \n",
    "\n",
    "        return result            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        \n",
    "        \"\"\"\n",
    "        難度適中\n",
    "        給一個 linked list 的 head, 和 int k\n",
    "        把這個 linked list 拆成 k 個 list\n",
    "        1. 每個 part 長度要盡可能一樣, 兩個 list 最多不能超過一個 node\n",
    "        2. list 也可以是 null (因為 k 可能比 list 長度還要大)\n",
    "        3. 每個 part 的 node 排序法要照原本的順序\n",
    "        4. 如果有 part 的長度比較長, 那這個 part 要排在前面\n",
    "        \"\"\"\n",
    "        \n",
    "        \"\"\"\n",
    "        想法:\n",
    "        1. 計算整個 list 的總長度: n\n",
    "        2. n / k = 代表每個 part 的長度(base_length)\n",
    "        3. 如果 n / k 不能整除, 代表有部分的 part 會有 extra node\n",
    "           n % k = 代表有幾個多出來的 node 可以加到部分的 part\n",
    "                   (題目有規定兩個 part 最多不能超過一個 node)\n",
    "           也可以想成: 有\"幾個 part\" 需要 extra node\n",
    "           \n",
    "        4. time: O(max(n, k))\n",
    "           k 可能會比 n 還要大, 在建立 list 的時候每個 part 都要走過一次\n",
    "        \n",
    "        5. 產生 k 個 part 的時候, 每一個 part 都是新的 list\n",
    "        \"\"\"\n",
    "        \n",
    "        length, cur = 0, head\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            length += 1 # cur 也有包含 head\n",
    "            \n",
    "        base_len, reminder = length // k, length % k\n",
    "        cur = head\n",
    "        result = []\n",
    "        \n",
    "        for i in range(k): # 每個 part 都要走過, 因為某些 part 可能是 empty list\n",
    "            result.append(cur) # 每個 part 都是新的 list\n",
    "            \n",
    "            for j in range(base_len - 1 + (1 if reminder else 0)):\n",
    "                # 每個 part 一開始就是 cur\n",
    "                # 只要走 base_len - 1 就可以走到 base_len 的那一個 node\n",
    "                if cur == None:\n",
    "                    break\n",
    "                cur = cur.next\n",
    "            \n",
    "            # 如果 reminder > 0, 代表這一個 part 有分到 extra node\n",
    "            # 分到了就得扣掉一個\n",
    "            reminder -= (1 if reminder else 0)\n",
    "        \n",
    "            if cur:\n",
    "                # 這個 part 最後要指到 null, 還要把 cur 往前推進給下一個 part\n",
    "                cur.next, cur = None, cur.next\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        length_link = 0\n",
    "        cur = head\n",
    "        result = []\n",
    "        while cur != None:\n",
    "            length_link = length_link + 1\n",
    "            cur = cur.next\n",
    "        base = length_link // k\n",
    "        more = length_link % k\n",
    "        nums_list = [base for i in range(0,k)]\n",
    "        for i in range(0,more):\n",
    "            nums_list[i] = nums_list[i] + 1\n",
    "        print(nums_list)\n",
    "        for i in range(k):\n",
    "            num =0\n",
    "            new_link = ListNode()\n",
    "            cur_new = new_link\n",
    "            while head != None:\n",
    "                cur_new.next = head\n",
    "                cur_new = cur_new.next\n",
    "                num = num + 1\n",
    "                head = head.next\n",
    "                if num == nums_list[i]:\n",
    "                    break\n",
    "            if cur_new != None:\n",
    "                cur_new.next = None\n",
    "            result.append(new_link.next)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        cnt = 0 \n",
    "        h_1 = head\n",
    "        while not(h_1 is None ) :\n",
    "            cnt += 1\n",
    "            h_1 = h_1.next\n",
    "        # print('len is ',cnt)\n",
    "        a , b = cnt // k , cnt % k\n",
    "        print(a,b)\n",
    "\n",
    "        res = []\n",
    "        if a == 0 :\n",
    "            while head :\n",
    "                res.append(head)\n",
    "                head = head.next\n",
    "                res[-1].next = None\n",
    "            res += [None]*(k-cnt)        \n",
    "            return res\n",
    "\n",
    "        last = ListNode(None,next=head)\n",
    "        for i in range(cnt):\n",
    "\n",
    "            if (i + 1)  <= (a + 1) * b :\n",
    "                m = i % (a+1)\n",
    "            else : \n",
    "                m = (i - (a+1)*b) % a\n",
    "            if m == 0 :\n",
    "                if res :\n",
    "                    last.next = None\n",
    "                res.append(head)\n",
    "            last = head\n",
    "            head = head.next\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        n = 0\n",
    "        ptr = head\n",
    "        while ptr:\n",
    "            n += 1\n",
    "            ptr = ptr.next \n",
    "        q, r = divmod(n, k)\n",
    "        length = [q] * k\n",
    "        for i in range(r):\n",
    "            length[i] += 1\n",
    "        res = []\n",
    "        ptr = head\n",
    "        for i in range(k):\n",
    "            m = length[i]\n",
    "            if ptr is None:\n",
    "                res.append(None)\n",
    "                continue\n",
    "            res.append(ptr)\n",
    "            pre = None\n",
    "            while m > 0:\n",
    "                pre = ptr\n",
    "                ptr = ptr.next\n",
    "                m -= 1\n",
    "            pre.next = None\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        n = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            n += 1\n",
    "        quotient, remainder = n // k, n % k\n",
    "\n",
    "        parts = [None for _ in range(k)]\n",
    "        i, curr = 0, head\n",
    "        while i < k and curr:\n",
    "            parts[i] = curr\n",
    "            part_size = quotient + (1 if i < remainder else 0)\n",
    "            for _ in range(part_size - 1):\n",
    "                curr = curr.next\n",
    "            next = curr.next\n",
    "            curr.next = None\n",
    "            curr = next\n",
    "            i += 1\n",
    "        return parts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        count = 0\n",
    "        p = head\n",
    "        while p:\n",
    "            count += 1\n",
    "            p = p.next\n",
    "        mean, rest = count // k, count % k\n",
    "        heads = [None] * k\n",
    "        heads[0] = head\n",
    "        fast = head\n",
    "        for i in range(1, k):\n",
    "            slow = ListNode(0, fast)\n",
    "            num  = mean + 1 if i <= rest else mean\n",
    "            while num > 0:\n",
    "                num -= 1\n",
    "                if not fast:\n",
    "                    break\n",
    "                slow = slow.next\n",
    "                fast = fast.next\n",
    "            heads[i] = fast\n",
    "            slow.next = None\n",
    "        return heads\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        if head is None:\n",
    "            return [None]*k\n",
    "        #计算链表长度\n",
    "        cur = head\n",
    "        count = 0\n",
    "        while cur:\n",
    "            count += 1\n",
    "            cur = cur.next\n",
    "        #长度\n",
    "        a = count // k \n",
    "        b = count % k\n",
    "        list_lens = []\n",
    "        #剩余部分添加到固定长度\n",
    "        for i in range(b):\n",
    "            list_lens.append(a + 1)\n",
    "        for i in range(k-b):\n",
    "            list_lens.append(a)\n",
    "        print(list_lens)\n",
    "        cur = head\n",
    "        index = 0\n",
    "        count = 0\n",
    "        start = head\n",
    "        result = []\n",
    "        while cur:\n",
    "            count += 1\n",
    "            if count == list_lens[index]:\n",
    "                count = 0\n",
    "                end = cur\n",
    "                cur = cur.next\n",
    "                end.next = None\n",
    "                result.append(start)\n",
    "                start = cur\n",
    "                index += 1\n",
    "            else:\n",
    "                cur = cur.next\n",
    "        if len(result) < k:\n",
    "            for i in range(k-len(result)):\n",
    "                result.append(None)\n",
    "        return result\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        p = head\n",
    "        n = 0\n",
    "        while p :\n",
    "            n += 1\n",
    "            p = p.next\n",
    "        basic = n // k\n",
    "        remain = n % k\n",
    "        ans = [None]*k\n",
    "        index = 0\n",
    "        cur = head\n",
    "        \n",
    "        while cur:\n",
    "            ans[index] = cur\n",
    "            last = None\n",
    "            curr_len = basic + 1 if index < remain else basic\n",
    "            for i in range(curr_len):\n",
    "                last = cur\n",
    "                cur = cur.next\n",
    "            last.next = None\n",
    "            index += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        # Benhao做法\n",
    "        length = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            length += 1\n",
    "        res = [None] * k\n",
    "        t, v = divmod(length, k)\n",
    "        cur, idx = head, 0\n",
    "        while cur:\n",
    "            res[idx] = cur\n",
    "            last = None\n",
    "            # idx < v这里很妙，代替了之前的暴力方法\n",
    "            for _ in range(t + (idx < v)):\n",
    "                last = cur\n",
    "                cur = cur.next\n",
    "            idx += 1\n",
    "            # 子链表尾断开\n",
    "            last.next = None\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        ans = [None for i in range(k)] \n",
    "        ans[0] = head\n",
    "        for i in range(1,k):\n",
    "            if ans[i-1]:\n",
    "                ans[i] = ans[i-1].next\n",
    "        while ans[k-1]:\n",
    "            for i in range(k-1):\n",
    "                ans[k-1] = ans[k-1].next\n",
    "                if not ans[k-1]:\n",
    "                    break\n",
    "                for j in range(i,k-1):\n",
    "                    ans[j] = ans[j].next\n",
    "            if ans[k-1]:\n",
    "                ans[k-1] = ans[k-1].next\n",
    "        for i in range(k-1,0,-1):\n",
    "            if ans[i-1]:\n",
    "                ans[i] = ans[i-1].next\n",
    "                ans[i-1].next = None\n",
    "        ans[0] = head\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        l = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            cur = cur.next \n",
    "            l += 1\n",
    "        quotient = l//k\n",
    "        remainder = l%k\n",
    "        ans = []\n",
    "        while head:\n",
    "            interval = quotient\n",
    "            if remainder:\n",
    "                remainder -= 1\n",
    "                interval += 1\n",
    "            ans.append(head)\n",
    "            for i in range(interval - 1):\n",
    "                head = head.next\n",
    "            t = head\n",
    "            head = t.next\n",
    "            t.next = None\n",
    "        while len(ans) < k:\n",
    "            ans.append(None)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        length=0\n",
    "        cur=head\n",
    "        while cur:\n",
    "            length+=1\n",
    "            cur=cur.next\n",
    "\n",
    "        count=length//k \n",
    "        left=length%k\n",
    "        \n",
    "        cur=head\n",
    "        res=[]\n",
    "        for _ in range(k):\n",
    "            res.append(cur)\n",
    "            temp=count+1 if left>0 else count\n",
    "            if cur:\n",
    "                for i in range(temp-1):\n",
    "                    cur=cur.next\n",
    "                nxt=cur.next\n",
    "                cur.next=None\n",
    "                cur=nxt\n",
    "                left-=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    # list of list里面放的是每段的head\n",
    "    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:\n",
    "        n = 0\n",
    "        node = head\n",
    "        while node:\n",
    "            n += 1\n",
    "            node = node.next\n",
    "        quotient, remainder = n // k, n % k\n",
    "\n",
    "        parts = [None for _ in range(k)]\n",
    "        i, curr = 0, head\n",
    "        while i < k and curr:\n",
    "            parts[i] = curr\n",
    "            part_size = quotient + (1 if i < remainder else 0)\n",
    "            for _ in range(part_size - 1):\n",
    "                curr = curr.next\n",
    "            next = curr.next\n",
    "            curr.next = None\n",
    "            curr = next\n",
    "            i += 1\n",
    "        return parts\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        n, cur = 0, head\n",
    "        part = []\n",
    "        while cur:\n",
    "            n += 1\n",
    "            cur = cur.next\n",
    "        # use a dummy node\n",
    "        q, r = n // k, n % k\n",
    "        cur = head \n",
    "        for _ in range(k):\n",
    "            dummy = ListNode()\n",
    "            pre = dummy\n",
    "            for _ in range(q + (r > 0)):\n",
    "                dummy.next, cur, dummy = cur, cur.next, cur\n",
    "            if r > 0:\n",
    "                r -= 1\n",
    "            dummy.next = None\n",
    "            part.append(pre.next)\n",
    "        return part\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def len_node(head:ListNode):\n",
    "    i = 0\n",
    "    while head:\n",
    "        i = i+1\n",
    "        head = head.next\n",
    "    return i\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        result = []\n",
    "        if k==1:\n",
    "            result.append(head)\n",
    "            return result\n",
    "        len_head = len_node(head)\n",
    "        result = [None]*k\n",
    "        cur = head\n",
    "        basic = len_head//k #先平分\n",
    "        remain = len_head%k #平分完之后剩余多少个\n",
    "        idx = 0\n",
    "        last = None\n",
    "        while cur:\n",
    "            result[idx] = cur\n",
    "            unit_loop_num = basic+1 if idx<remain else basic#单idx小于余数的时候要多加1个，否则就是等于平分的个数\n",
    "            for _ in range(unit_loop_num):\n",
    "                last = cur\n",
    "                cur = cur.next\n",
    "            last.next = None\n",
    "            idx = idx+1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        res = []\n",
    "        if not head:\n",
    "            for _ in range(k):\n",
    "                res.append(None)\n",
    "            return res\n",
    "        n = 0\n",
    "        tmp = head\n",
    "        pre_head = ListNode(0)\n",
    "        pre_head.next = head\n",
    "        while tmp:\n",
    "            n += 1\n",
    "            tmp = tmp.next\n",
    "        part = n // k\n",
    "        left = n - k * part\n",
    "        while head:\n",
    "            if left:\n",
    "                loop = part + 1\n",
    "            else:\n",
    "                loop = part\n",
    "            left -= 1 if left >0 else 0\n",
    "            tmp = head\n",
    "            for _ in range(loop):\n",
    "                pre_head = head\n",
    "                head = head.next\n",
    "            nxt_head = head\n",
    "            pre_head.next = None\n",
    "            res.append(tmp)\n",
    "            head = nxt_head\n",
    "        if len(res) != k:\n",
    "            need_add = k - len(res)\n",
    "            for _ in range(need_add):\n",
    "                res.append(None)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        #先计算链表长度\n",
    "        length=0\n",
    "        ans=head\n",
    "        while ans:\n",
    "            length=length+1\n",
    "            ans=ans.next\n",
    "        part_length=length//k\n",
    "        remain=length % k\n",
    "        answer=[None]*k\n",
    "        tmp=head\n",
    "        for i in range(k):\n",
    "            if tmp:\n",
    "                answer[i]=tmp\n",
    "                if i<remain:\n",
    "                    this_length=part_length+1\n",
    "                else:\n",
    "                    this_length=part_length\n",
    "                for j in range(this_length-1):\n",
    "                    tmp=tmp.next\n",
    "                tmp2=tmp.next\n",
    "                tmp.next=None\n",
    "                tmp=tmp2\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        cnt = 0 \n",
    "        h_1 = head\n",
    "        while not(h_1 is None ) :\n",
    "            cnt += 1\n",
    "            h_1 = h_1.next\n",
    "        # print('len is ',cnt)\n",
    "        a , b = cnt // k , cnt % k\n",
    "        # print(a,b)\n",
    "\n",
    "        res = []\n",
    "        if a == 0 :\n",
    "            while head :\n",
    "                res.append(head)\n",
    "                head = head.next\n",
    "                res[-1].next = None\n",
    "            res += [None]*(k-cnt)        \n",
    "            return res\n",
    "\n",
    "        last = ListNode(None,next=head)\n",
    "        for i in range(cnt):\n",
    "\n",
    "            if (i + 1)  <= (a + 1) * b :\n",
    "                m = i % (a+1)\n",
    "            else : \n",
    "                m = (i - (a+1)*b) % a\n",
    "            if m == 0 :\n",
    "                if res :\n",
    "                    last.next = None\n",
    "                res.append(head)\n",
    "            last = head\n",
    "            head = head.next\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        #拆分链表\n",
    "        n=0\n",
    "        node=head\n",
    "        while node:\n",
    "            n+=1\n",
    "            node=node.next\n",
    "        a,b=n//k,n%k\n",
    "        list1=[None for _ in range(k)]\n",
    "        i,cur=0,head\n",
    "        #开始为每个数组区间录入头节点\n",
    "        while i<k and cur:\n",
    "            #录入头节点\n",
    "            list1[i]=cur\n",
    "            #计算链表长度\n",
    "            size=a+(1 if i<b else 0)\n",
    "            for _ in range(size-1):\n",
    "                #移动节点，使该区间的链表长度等于 size\n",
    "                cur=cur.next\n",
    "            #保存下一个链表区间的头节点\n",
    "            temp=cur.next\n",
    "            #断开这一段已经遍历过的链表\n",
    "            cur.next=None\n",
    "            #更新粗人指针\n",
    "            cur=temp\n",
    "            #更新计数器i\n",
    "            i+=1\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        def linklen(head):\n",
    "            L = 0\n",
    "            while head:\n",
    "                L += 1\n",
    "                head = head.next\n",
    "            return L\n",
    "\n",
    "        L = linklen(head)\n",
    "        n = floor(L / k)\n",
    "        r = L % k\n",
    "\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            dummy = ListNode()\n",
    "            cur = dummy\n",
    "            for j in range(n + int(r > 0)):\n",
    "                cur.next = head \n",
    "                head = head.next\n",
    "                cur = cur.next\n",
    "            cur.next = None\n",
    "            ans.append(dummy.next)\n",
    "            r -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "\n",
    "\n",
    "        len = 0\n",
    "        curr = head\n",
    "        while curr:\n",
    "            len += 1\n",
    "            curr = curr.next\n",
    "        \n",
    "        width = len // k\n",
    "        reaminder = len % k\n",
    "\n",
    "        curr = head\n",
    "        res = [None] * k\n",
    "\n",
    "        for i in range(k):\n",
    "            newHead = curr\n",
    "            realWidth = width if i < reaminder else width - 1\n",
    "\n",
    "            for j in range(realWidth):\n",
    "                if curr: curr = curr.next\n",
    "            if curr:\n",
    "                next = curr.next\n",
    "                curr.next = None\n",
    "                curr = next\n",
    "            res[i] = newHead\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:\n",
    "        n = 0\n",
    "        node = head\n",
    "        while node:\n",
    "            n += 1\n",
    "            node = node.next\n",
    "        quotient, remainder = n // k, n % k\n",
    "\n",
    "        parts = [None for _ in range(k)]\n",
    "        i, curr = 0, head\n",
    "        while i < k and curr:\n",
    "            parts[i] = curr\n",
    "            part_size = quotient + (1 if i < remainder else 0)\n",
    "            for _ in range(part_size - 1):\n",
    "                curr = curr.next\n",
    "            next = curr.next\n",
    "            curr.next = None\n",
    "            curr = next\n",
    "            i += 1\n",
    "        return parts\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        p = head\n",
    "        n = 0\n",
    "        while p :\n",
    "            n += 1\n",
    "            p = p.next\n",
    "        each_len, _mod = n // k, n % k\n",
    "        p = head\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            new_head = p \n",
    "            tmp = i < _mod\n",
    "            for j in range(each_len + tmp - 1): \n",
    "                if p:\n",
    "                    p = p.next\n",
    "            if p:\n",
    "                cur_p = p \n",
    "                p = p.next\n",
    "                cur_p.next = None \n",
    "            res.append(new_head)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        #拆分链表\n",
    "        n=0\n",
    "        node=head\n",
    "        while node:\n",
    "            n+=1\n",
    "            node=node.next\n",
    "        a,b=n//k,n%k\n",
    "        list1=[None for _ in range(k)]\n",
    "        i,cur=0,head\n",
    "        #开始为每个数组区间录入头节点\n",
    "        while i<k and cur:\n",
    "            #录入头节点\n",
    "            list1[i]=cur\n",
    "            #计算链表长度\n",
    "            size=a+(1 if i<b else 0)\n",
    "            for _ in range(size-1):\n",
    "                #移动节点，使该区间的链表长度等于 size\n",
    "                cur=cur.next\n",
    "            #保存下一个链表区间的头节点\n",
    "            temp=cur.next\n",
    "            #断开这一段已经遍历过的链表\n",
    "            cur.next=None\n",
    "            #更新粗人指针\n",
    "            cur=temp\n",
    "            #更新计数器i\n",
    "            i+=1\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        \n",
    "        \"\"\"\n",
    "        難度適中\n",
    "        給一個 linked list 的 head, 和 int k\n",
    "        把這個 linked list 拆成 k 個 list\n",
    "        1. 每個 part 長度要盡可能一樣, 兩個 list 最多不能超過一個 node\n",
    "        2. list 也可以是 null (因為 k 可能比 list 長度還要大)\n",
    "        3. 每個 part 的 node 排序法要照原本的順序\n",
    "        4. 如果有 part 的長度比較長, 那這個 part 要排在前面\n",
    "        \"\"\"\n",
    "        \n",
    "        \"\"\"\n",
    "        想法:\n",
    "        1. 計算整個 list 的總長度: n\n",
    "        2. n / k = 代表每個 part 的長度(base_length)\n",
    "        3. 如果 n / k 不能整除, 代表有部分的 part 會有 extra node\n",
    "           n % k = 代表有幾個多出來的 node 可以加到部分的 part\n",
    "                   (題目有規定兩個 part 最多不能超過一個 node)\n",
    "           也可以想成: 有\"幾個 part\" 需要 extra node\n",
    "           \n",
    "        4. time: O(max(n, k))\n",
    "           k 可能會比 n 還要大, 在建立 list 的時候每個 part 都要走過一次\n",
    "        \n",
    "        5. 產生 k 個 part 的時候, 每一個 part 都是新的 list\n",
    "        \"\"\"\n",
    "        \n",
    "        length, cur = 0, head\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            length += 1 # cur 也有包含 head\n",
    "            \n",
    "        base_len, reminder = length // k, length % k\n",
    "        cur = head\n",
    "        result = []\n",
    "        \n",
    "        for i in range(k): # 每個 part 都要走過, 因為某些 part 可能是 empty list\n",
    "            result.append(cur) # 每個 part 都是新的 list\n",
    "            \n",
    "            for j in range(base_len - 1 + (1 if reminder else 0)):\n",
    "                # 每個 part 一開始就是 cur\n",
    "                # 只要走 base_len - 1 就可以走到 base_len 的那一個 node\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "            \n",
    "            # 如果 reminder > 0, 代表這一個 part 有分到 extra node\n",
    "            # 分到了就得扣掉一個\n",
    "            reminder -= (1 if reminder else 0)\n",
    "        \n",
    "            if cur:\n",
    "                # 這個 part 最後要指到 null, 還要把 cur 往前推進給下一個 part\n",
    "                cur.next, cur = None, cur.next\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        head_len = 0\n",
    "        temp_head = head\n",
    "        while temp_head:\n",
    "            head_len += 1\n",
    "            temp_head = temp_head.next\n",
    "        \n",
    "        min_len = head_len // k\n",
    "        max_len = min_len + 1\n",
    "        max_nums = head_len % k\n",
    "        min_nums = k - max_nums\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for i in range(max_nums):\n",
    "            temp_res = head\n",
    "            temp_real_res = temp_res\n",
    "            for j in range(max_len):\n",
    "                head = head.next\n",
    "                if j+1 == max_len:\n",
    "                    temp_res.next = None\n",
    "                else:\n",
    "                    temp_res = temp_res.next\n",
    "            res.append(temp_real_res)\n",
    "        \n",
    "        for i in range(min_nums):\n",
    "            temp_res = head\n",
    "            temp_real_res = temp_res\n",
    "            if not temp_res:\n",
    "                res.append(temp_res)\n",
    "                continue\n",
    "            for j in range(min_len):\n",
    "                head = head.next\n",
    "                if j+1 == min_len:\n",
    "                    temp_res.next = None\n",
    "                else:\n",
    "                    temp_res = temp_res.next\n",
    "                \n",
    "            res.append(temp_real_res)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        #拆分链表\n",
    "        n=0\n",
    "        node=head\n",
    "        #遍历链表得到链表长度\n",
    "        while node:\n",
    "            n+=1\n",
    "            node=node.next\n",
    "        a,b=n//k,n%k\n",
    "        list1=[None for _ in range(k)]\n",
    "        i,cur=0,head\n",
    "        while i<k and cur:\n",
    "            list1[i]=cur\n",
    "            size=a+(1 if i<b else 0)\n",
    "            for _ in range(size-1):\n",
    "                cur=cur.next\n",
    "            #保留这一段末尾结点的下一个节点，也就是下一段链表的头结点\n",
    "            temp=cur.next\n",
    "            #将尾结点的指针滞空\n",
    "            cur.next=None\n",
    "            #将指针移动到下一个节点\n",
    "            cur=temp\n",
    "            i+=1\n",
    "        return list1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:\n",
    "        cur = root\n",
    "        lth = 0\n",
    "        while cur:\n",
    "            lth += 1\n",
    "            cur = cur.next\n",
    "        n = lth//k\n",
    "        longer = lth%k\n",
    "        res = [n+1]*longer+[n]*(k-longer)\n",
    "        pre = ListNode(None)\n",
    "        cur = root\n",
    "        for i,num in enumerate(res):\n",
    "            if pre:\n",
    "                pre.next = None\n",
    "            res[i] = cur\n",
    "            for _ in range(num):\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        \n",
    "        # 计算链表长度\n",
    "        l = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            l += 1\n",
    "            cur = cur.next\n",
    "\n",
    "        # 计算每段的平均长度\n",
    "        avg_l = l // k\n",
    "        # 计算有几段较长\n",
    "        n_longer = l % k\n",
    "\n",
    "        # 切分链表\n",
    "        res = [None for _ in range(k)]    # 创建一个长度为k的链表\n",
    "        cur = head\n",
    "        for i in range(k):\n",
    "            if cur == None:\n",
    "                break\n",
    "            cur_l = avg_l + (1 if i < n_longer else 0)\n",
    "            res[i] = cur\n",
    "            for _ in range (0, cur_l - 1, 1):\n",
    "                cur = cur.next\n",
    "\n",
    "            if cur:\n",
    "                tmp = cur.next\n",
    "                cur.next = None\n",
    "                cur = tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        p = head\n",
    "        n = 0\n",
    "        while p :\n",
    "            n += 1\n",
    "            p = p.next\n",
    "        each_len, _mod = n // k, n % k\n",
    "        p = head\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            new_head = p \n",
    "            tmp = i < _mod\n",
    "            for j in range(each_len + tmp - 1): \n",
    "                if p:\n",
    "                    p = p.next\n",
    "            if p:\n",
    "                cur_p = p \n",
    "                p = p.next\n",
    "                cur_p.next = None \n",
    "            res.append(new_head)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "\n",
    "        # 1. 记录链表的长度\n",
    "        n = 0\n",
    "        p = head\n",
    "        while p:\n",
    "            n += 1\n",
    "            p = p.next\n",
    "            \n",
    "\n",
    "        # 2. 根据链表的长度，分别求出答案数组中每个部分应该保存的节点数\n",
    "        anygroup = n // k\n",
    "        res_node = n % k #  多出来的只能放在前面几个组，并且每个组至多放一个\n",
    "        res = [ None for _ in range(k)]\n",
    "\n",
    "        cur = head\n",
    "        i = 0\n",
    "        while cur and i < k:\n",
    "            res[i] = cur\n",
    "            part_size = anygroup + (1 if i < res_node else 0)\n",
    "            for _ in range(part_size - 1):\n",
    "                cur = cur.next\n",
    "            cur.next, cur = None, cur.next\n",
    "            i += 1\n",
    "        return res\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        ans = []\n",
    "        now = head\n",
    "        n = 0\n",
    "        while not now is None:\n",
    "            n += 1\n",
    "            now = now.next\n",
    "        length = n // k\n",
    "        longer_num = n % k\n",
    "\n",
    "        now = head\n",
    "        top = head\n",
    "        tmp = 0\n",
    "        while not now is None:\n",
    "            nxt = now.next\n",
    "            tmp += 1\n",
    "            # print(now.val, tmp, length)\n",
    "            if (longer_num > 0 and tmp == length+1) or (longer_num <= 0 and tmp == length):\n",
    "                now.next = None\n",
    "                ans.append(top)\n",
    "                top = nxt\n",
    "                tmp = 0\n",
    "                longer_num -= 1\n",
    "            now = nxt\n",
    "        if len(ans) < k:\n",
    "            ans += [None]*(k-len(ans))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        n=0\n",
    "        node=head\n",
    "        while node:\n",
    "            n+=1\n",
    "            node=node.next\n",
    "        q,r=divmod(n,k)\n",
    "        parts=[None for _ in range(k)]\n",
    "        i,cur=0,head\n",
    "        while i<k and cur:\n",
    "            parts[i]=cur\n",
    "            partsSize=q +(1 if i<r else 0)\n",
    "            for _ in range(partsSize-1):\n",
    "                cur=cur.next\n",
    "            next=cur.next\n",
    "            cur.next=None\n",
    "            cur=next\n",
    "            i+=1\n",
    "        return parts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        n=0\n",
    "        node=head\n",
    "        #遍历链表得到链表长度\n",
    "        while node:\n",
    "            n+=1\n",
    "            node=node.next\n",
    "        a,b=n//k,n%k\n",
    "        list1=[None for _ in range(k)]\n",
    "        i,cur=0,head\n",
    "        while i<k and cur:\n",
    "            list1[i]=cur\n",
    "            size=a+(1 if i<b else 0)\n",
    "            for _ in range(size-1):\n",
    "                cur=cur.next\n",
    "            #保留这一段末尾结点的下一个节点，也就是下一段链表的头结点\n",
    "            temp=cur.next\n",
    "            #将尾结点的指针滞空\n",
    "            cur.next=None\n",
    "            #将指针移动到下一个节点\n",
    "            cur=temp\n",
    "            i+=1\n",
    "        return list1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        count = 0\n",
    "        p = head\n",
    "        while p:\n",
    "            count += 1\n",
    "            p = p.next\n",
    "        mean, rest = count // k, count % k\n",
    "        heads = [None] * k\n",
    "        heads[0] = head\n",
    "        fast = head\n",
    "        for i in range(1, k):\n",
    "            slow = ListNode(0, fast)\n",
    "            num  = mean + 1 if i <= rest else mean\n",
    "            while num > 0:\n",
    "                num -= 1\n",
    "                if not fast:\n",
    "                    break\n",
    "                slow = slow.next\n",
    "                fast = fast.next\n",
    "            heads[i] = fast\n",
    "            slow.next = None\n",
    "        return heads\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        n = 0\n",
    "        node = head\n",
    "        while node:\n",
    "            n += 1\n",
    "            node = node.next\n",
    "        quotient, remainder = n // k, n % k\n",
    "\n",
    "        parts = [None for _ in range(k)]\n",
    "        i, curr = 0, head\n",
    "        while i < k and curr:\n",
    "            parts[i] = curr\n",
    "            part_size = quotient + (1 if i < remainder else 0)\n",
    "            for _ in range(part_size - 1):\n",
    "                curr = curr.next\n",
    "            next = curr.next\n",
    "            curr.next = None\n",
    "            curr = next\n",
    "            i += 1\n",
    "        return parts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        l = 0\n",
    "        cur = head\n",
    "        ans = []\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            l+=1\n",
    "        quoient = l//k\n",
    "        remainder = l%k\n",
    "        while head:\n",
    "            interval = quoient\n",
    "            if remainder:\n",
    "                remainder -= 1\n",
    "                interval += 1\n",
    "            ans.append(head)\n",
    "            for i in range(interval-1):\n",
    "                head = head.next\n",
    "            if not head.next:break\n",
    "            head.next,head = None,head.next\n",
    "        while len(ans)<k:\n",
    "            ans.append(None)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "  def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "    r = []\n",
    "    while head:\n",
    "      r.append(head)\n",
    "      head = head.next\n",
    "    l = len(r)\n",
    "    i = l // k\n",
    "    m = l % k\n",
    "    ret = []\n",
    "    p = 0\n",
    "    while k > 0:\n",
    "      if p < l:\n",
    "        ret.append(r[p])\n",
    "        p += i\n",
    "        if m > 0:\n",
    "            m -= 1\n",
    "        else:\n",
    "            p -= 1\n",
    "        r[p].next = None\n",
    "        p += 1\n",
    "      else:\n",
    "        ret.append(None)\n",
    "      k -= 1\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def count(self,head):\n",
    "        count = 0\n",
    "        p = head\n",
    "        while p:\n",
    "            count += 1\n",
    "            p = p.next\n",
    "        return count\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        length = self.count(head)\n",
    "        quotient,remainder = length // k,length % k\n",
    "        res = [None for _ in range(k)]\n",
    "        i,cur = 0,head\n",
    "        while i < k and cur:\n",
    "            res[i] = cur\n",
    "            part_size = quotient + (1 if i < remainder else 0)\n",
    "            for _ in range(part_size - 1):\n",
    "                cur = cur.next\n",
    "            next = cur.next\n",
    "            cur.next = None\n",
    "            cur = next\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "\n",
    "        # 第一次遍历找到最大长度n\n",
    "        n = 0\n",
    "        node = head\n",
    "        while node:\n",
    "            n += 1\n",
    "            node = node.next\n",
    "\n",
    "        a,b = n//k, n%k\n",
    "\n",
    "        res = [None for _ in range(k)]\n",
    "        i,curr = 0,head\n",
    "        while i<k and curr:  # i从0-k-1，代表当前组数，curr代表node\n",
    "            res[i] = curr\n",
    "            curr_size = a + (1 if i<b else 0)  # 如果前b组，那么每组有a+1个元素，之后每组a个\n",
    "            for _ in range(curr_size-1):\n",
    "                curr = curr.next\n",
    "            next_curr = curr.next\n",
    "            curr.next = None\n",
    "            curr = next_curr\n",
    "\n",
    "            i += 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        # res = [None for _ in range(k)]\n",
    "        # p = [[] for _ in range(k)]\n",
    "        # n = 0 \n",
    "        # p = head \n",
    "        # while p:\n",
    "        #     n += 1\n",
    "        #     p = p.next\n",
    "        # a, b = n//k, n%k\n",
    "        # print(n, a, b)\n",
    "        # i = count = 0\n",
    "        # while head:\n",
    "        #     res[i] = head \n",
    "        #     last = None \n",
    "        #     for _ in range(a+(b>i)):\n",
    "        #         last = head \n",
    "        #         head = head.next\n",
    "        #     i += 1\n",
    "        #     last.next = None\n",
    "        # return res \n",
    "\n",
    "        # -----------------------------------\n",
    "        res = [None for _ in range(k)]\n",
    "        res[0] = head\n",
    "        for i in range(1, k):\n",
    "            if res[i-1]:\n",
    "                res[i] = res[i-1].next\n",
    "        while res[-1]:\n",
    "            for i in range(k-1):\n",
    "                res[-1] = res[-1].next\n",
    "                if not res[-1]:\n",
    "                    break \n",
    "                for j in range(i, k-1):\n",
    "                    res[j] = res[j].next\n",
    "            if res[-1]:\n",
    "                res[-1] = res[-1].next\n",
    "        for i in range(k-1, 0, -1):\n",
    "            if res[i-1]:\n",
    "                res[i] = res[i-1].next\n",
    "                res[i-1].next = None \n",
    "        res[0] = head\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        cur, l = head, 0\n",
    "        while cur:\n",
    "            l += 1\n",
    "            cur = cur.next\n",
    "        each, remain = l // k, l % k\n",
    "        cur, ans, idx = head, [None] * k, 0\n",
    "        while cur:\n",
    "            ans[idx] = cur\n",
    "            last = None\n",
    "            for i in range(each + (idx < remain)):\n",
    "                last = cur\n",
    "                cur = cur.next\n",
    "            idx += 1\n",
    "            last.next = None\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        pre = head\n",
    "        l = 0\n",
    "        while pre:\n",
    "            l += 1\n",
    "            pre = pre.next\n",
    "        each, remain = l // k, l % k\n",
    "        cur, ans, idx = head, [None] * k, 0\n",
    "        while cur:\n",
    "            ans[idx] = cur\n",
    "            last = None\n",
    "            for i in range(each + (idx < remain)):\n",
    "                last = cur\n",
    "                cur = cur.next\n",
    "            idx +=1\n",
    "            last.next = None\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        head_c = head\n",
    "        length = 0\n",
    "        while head_c:\n",
    "\n",
    "            head_c = head_c.next\n",
    "            length +=1\n",
    "        res = []\n",
    "        if length//k == 0:\n",
    "            node = head\n",
    "            while head:\n",
    "                node = head\n",
    "                head = head.next\n",
    "                node.next = None\n",
    "                res.append(node)\n",
    "            while len(res)<k:\n",
    "                res.append(None)\n",
    "        else:\n",
    "            remian = length%k\n",
    "            count = length//k\n",
    "            while len(res)<k:\n",
    "                if remian>0:\n",
    "                    node = head\n",
    "                    for i in range(count):\n",
    "                        head = head.next\n",
    "                    tail = head\n",
    "                    head = head.next\n",
    "                    tail.next = None\n",
    "                    res.append(node)\n",
    "                    remian-=1\n",
    "                else:\n",
    "                    node = head\n",
    "                    for i in range(count-1):\n",
    "                        head = head.next\n",
    "                    tail = head\n",
    "                    head = head.next\n",
    "                    tail.next = None\n",
    "                    res.append(node)\n",
    "                    remian-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        cnt = 0 \n",
    "        h_1 = head\n",
    "        while not(h_1 is None ) :\n",
    "            cnt += 1\n",
    "            h_1 = h_1.next\n",
    "        # print('len is ',cnt)\n",
    "        a , b = cnt // k , cnt % k\n",
    "        # print(a,b)\n",
    "\n",
    "        res = []\n",
    "        if a == 0 :\n",
    "            while head :\n",
    "                res.append(head)\n",
    "                head = head.next\n",
    "                res[-1].next = None\n",
    "            res += [None]*(k-cnt)        \n",
    "            return res\n",
    "\n",
    "        last = ListNode(None,next=head)\n",
    "        for i in range(cnt):\n",
    "\n",
    "            if (i + 1)  <= (a + 1) * b :\n",
    "                m = i % (a+1)\n",
    "            else : \n",
    "                m = (i - (a+1)*b) % a\n",
    "            if m == 0 :\n",
    "                if res :\n",
    "                    last.next = None\n",
    "                res.append(head)\n",
    "            last = head\n",
    "            head = head.next\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        length, node = 0, head\n",
    "        while node:\n",
    "            length += 1\n",
    "            node = node.next\n",
    "        \n",
    "        base, remainder = length // k, length % k\n",
    "        i = 0\n",
    "        cur = head\n",
    "        part = [None for _ in range(k)]\n",
    "        while i < k and cur:\n",
    "            part[i] = cur\n",
    "            partial_size = base + (1 if i < remainder else 0)\n",
    "            for _ in range(partial_size - 1):\n",
    "                cur = cur.next\n",
    "            tmp = cur.next\n",
    "            cur.next = None\n",
    "            cur = tmp\n",
    "            i += 1\n",
    "        return part"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        \n",
    "        # k > len(head), then we put each number in a list \n",
    "        # k <= len(head)\n",
    "        \n",
    "        # 如果node的数量 <= k 我们就创建k个盒子，每个盒子里面放1个node\n",
    "        # 如果node的数量 >k 我们就创建k个盒子，第一个盒子放最多的node，其他盒子放一样的node\n",
    "\n",
    "        # 得到node的数量 - traverse链表\n",
    "        # 10 // 3 = 3  就是最小的盒子要装的数量，余数2就是有多少大盒子的数量\n",
    "        # 10 % 3 = 1 \n",
    "\n",
    "        \n",
    "        count = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            count += 1\n",
    "            cur = cur.next \n",
    "        \n",
    "        quotient = count // k \n",
    "        remainder = count % k \n",
    "        \n",
    "        res = [None for i in range(k)]\n",
    "        i = 0 \n",
    "        cur = head\n",
    "        while i < k and cur:\n",
    "            res[i] = cur \n",
    "            for j in range(0, quotient + (1 if i < remainder else 0)-1):\n",
    "                cur = cur.next \n",
    "            temp = cur.next \n",
    "            cur.next = None \n",
    "            cur = temp \n",
    "            i += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, root: ListNode, k: int):\n",
    "        total_len = 0\n",
    "        cur = root\n",
    "        while cur:\n",
    "            total_len += 1\n",
    "            cur = cur.next\n",
    "        length = total_len // k   # 每段的基础长度\n",
    "        m = total_len % k         # 前 l 段需要在基础长度上+1\n",
    "        res = []\n",
    "        cur = root\n",
    "        for i in range(k):\n",
    "            res.append(cur)\n",
    "            size = length + (1 if m > 0 else 0)   # 算出每段的长度\n",
    "            if cur:   # 这里判断cur是否存在，防止cur.next不存在报错\n",
    "                for j in range(size-1):\n",
    "                    cur = cur.next\n",
    "                m -= 1\n",
    "                tmp = cur.next   # 把后面一段截掉，后面一段需在后面继续划分\n",
    "                cur.next = None\n",
    "                cur = tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        my_len = 0\n",
    "        pointer = head\n",
    "    \n",
    "        while pointer != None:\n",
    "            \n",
    "            my_len += 1           \n",
    "            pointer = pointer.next\n",
    "    \n",
    "        length_list = [my_len // k] * k\n",
    "        for i in range(my_len % k):\n",
    "            length_list[i] += 1\n",
    "        result = []\n",
    "        my_iter = head\n",
    "        for i in range(len(length_list)):\n",
    "            new_head = my_iter\n",
    "            if length_list[i] == 0:\n",
    "                result.append(None)\n",
    "            else:\n",
    "                for j in range(length_list[i] - 1):\n",
    "                    if my_iter:\n",
    "                        my_iter = my_iter.next\n",
    "                \n",
    "                temp_point = my_iter\n",
    "                if my_iter.next:\n",
    "                    my_iter = my_iter.next\n",
    "                if temp_point:\n",
    "                    temp_point.next = None\n",
    "\n",
    "                result.append(new_head)\n",
    "        return result\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "\n",
    "        # 1. 记录链表的长度\n",
    "        n = 0\n",
    "        p = head\n",
    "        while p:\n",
    "            n += 1\n",
    "            p = p.next\n",
    "            \n",
    "\n",
    "        # 2. 根据链表的长度，分别求出答案数组中每个部分应该保存的节点数\n",
    "        anygroup = n // k\n",
    "        res_node = n % k\n",
    "        res = [ None for _ in range(k)]\n",
    "\n",
    "        cur = head\n",
    "        i = 0\n",
    "        while cur and i < k:\n",
    "            res[i] = cur\n",
    "            part_size = anygroup + (1 if i < res_node else 0)\n",
    "            for _ in range(part_size - 1):\n",
    "                cur = cur.next\n",
    "            cur.next, cur = None, cur.next\n",
    "            i += 1\n",
    "        return res\n",
    "                    \n",
    "\n",
    "        # n = 0\n",
    "        # node = head\n",
    "        # while node:\n",
    "        #     n += 1\n",
    "        #     node = node.next\n",
    "        # quotient, remainder = n // k, n % k\n",
    "\n",
    "        # parts = [None for _ in range(k)]\n",
    "        # i, curr = 0, head\n",
    "        # while i < k and curr:\n",
    "        #     parts[i] = curr\n",
    "        #     part_size = quotient + (1 if i < remainder else 0)\n",
    "        #     for _ in range(part_size - 1):\n",
    "        #         curr = curr.next\n",
    "        #     next = curr.next\n",
    "        #     curr.next = None\n",
    "        #     curr = next\n",
    "        #     i += 1\n",
    "        # return parts\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        count = 0\n",
    "        while cur and cur.next:\n",
    "            count += 1\n",
    "            cur = cur.next\n",
    "        chunck = count //k\n",
    "        extra = count % k\n",
    "        buckets = [chunck] * k # [0, 0, 0, 0, 0]\n",
    "        for i in range(extra): # [1, 1, 1, 0, 0]\n",
    "            buckets[i] += 1\n",
    "\n",
    "        res = []\n",
    "        pre, cur = dummy, dummy.next\n",
    "        for i, item in enumerate(buckets):\n",
    "            res.append(cur)\n",
    "            for _ in range(item):\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "            pre.next = None\n",
    "        return res\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        length = 0\n",
    "        iterator = head\n",
    "        while iterator:\n",
    "            iterator = iterator.next\n",
    "            length += 1\n",
    "        \n",
    "        n_per_group = length // k\n",
    "        overflow = length % k\n",
    "        # print(n_per_group, overflow)\n",
    "\n",
    "        iterator = head\n",
    "        ans = []\n",
    "        for _ in range(k):\n",
    "            current_head = iterator\n",
    "            for ii in range(n_per_group):\n",
    "                iterator = iterator.next\n",
    "            \n",
    "            # print(iterator)\n",
    "            if overflow != 0:\n",
    "                iterator = iterator.next\n",
    "                overflow -= 1\n",
    "            \n",
    "            ans.append(current_head)\n",
    "            prev = iterator\n",
    "        \n",
    "        for ii in range(len(ans) - 1):\n",
    "            next_head = ans[ii + 1]\n",
    "            iterator = ans[ii]\n",
    "            while iterator != None and iterator.next != next_head:\n",
    "                iterator = iterator.next\n",
    "            \n",
    "            if iterator != None:\n",
    "                iterator.next = None\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        my_len = 0\n",
    "        pointer = head\n",
    "    \n",
    "        while pointer != None:\n",
    "            \n",
    "            my_len += 1           \n",
    "            pointer = pointer.next\n",
    "    \n",
    "        length_list = [my_len // k] * k\n",
    "        for i in range(my_len % k):\n",
    "            length_list[i] += 1\n",
    "        result = []\n",
    "        my_iter = head\n",
    "        for i in range(len(length_list)):\n",
    "            new_head = my_iter\n",
    "            if length_list[i] == 0:\n",
    "                result.append(None)\n",
    "            else:\n",
    "                for j in range(length_list[i] - 1):\n",
    "                    if my_iter:\n",
    "                        my_iter = my_iter.next\n",
    "                \n",
    "                temp_point = my_iter\n",
    "                if my_iter.next:\n",
    "                    my_iter = my_iter.next\n",
    "                if temp_point:\n",
    "                    temp_point.next = None\n",
    "\n",
    "                result.append(new_head)\n",
    "        return result\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        result = []\n",
    "        if head is None:\n",
    "            for i in range(k):\n",
    "                result.append(None)\n",
    "            return result\n",
    "        #计算链表长度\n",
    "        cur = head\n",
    "        count = 0\n",
    "        while cur:\n",
    "            count += 1\n",
    "            cur = cur.next\n",
    "        \n",
    "        #长度\n",
    "        a = count // k \n",
    "        b = count % k\n",
    "        list_lens = []\n",
    "        #剩余部分添加到固定长度\n",
    "        for i in range(b):\n",
    "            list_lens.append(a + 1)\n",
    "        for i in range(k-b):\n",
    "            list_lens.append(a)\n",
    "        \n",
    "        cur = head\n",
    "        start = head\n",
    "        for lenght in list_lens:\n",
    "            print(\"lenght={0}\".format(lenght))\n",
    "            for i in range(lenght-1):\n",
    "                if cur is not None:\n",
    "                    cur = cur.next\n",
    "\n",
    "            result.append(start)\n",
    "            if cur is not None:\n",
    "                print(cur.val)\n",
    "                start = cur.next\n",
    "                cur.next = None\n",
    "                cur = start\n",
    "            \n",
    "        return result\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        \n",
    "        \"\"\"\n",
    "        難度適中\n",
    "        給一個 linked list 的 head, 和 int k\n",
    "        把這個 linked list 拆成 k 個 list\n",
    "        1. 每個 part 長度要盡可能一樣, 兩個 list 最多不能超過一個 node\n",
    "        2. list 也可以是 null (因為 k 可能比 list 長度還要大)\n",
    "        3. 每個 part 的 node 排序法要照原本的順序\n",
    "        4. 如果有 part 的長度比較長, 那這個 part 要排在前面\n",
    "        \"\"\"\n",
    "        \n",
    "        \"\"\"\n",
    "        想法:\n",
    "        1. 計算整個 list 的總長度: n\n",
    "        2. n / k = 代表每個 part 的長度(base_length)\n",
    "        3. 如果 n / k 不能整除, 代表有部分的 part 會有 extra node\n",
    "           n % k = 代表有幾個多出來的 node 可以加到部分的 part\n",
    "                   (題目有規定兩個 part 最多不能超過一個 node)\n",
    "           也可以想成: 有\"幾個 part\" 需要 extra node\n",
    "           \n",
    "        4. time: O(max(n, k))\n",
    "           k 可能會比 n 還要大, 在建立 list 的時候每個 part 都要走過一次\n",
    "        \n",
    "        5. 產生 k 個 part 的時候, 每一個 part 都是新的 list\n",
    "        \"\"\"\n",
    "        \n",
    "        length, cur = 0, head\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            length += 1 # cur 也有包含 head\n",
    "            \n",
    "        base_len, reminder = length // k, length % k\n",
    "        cur = head\n",
    "        result = []\n",
    "        \n",
    "        for i in range(k): # 每個 part 都要走過, 因為某些 part 可能是 empty list\n",
    "            result.append(cur) # 每個 part 都是新的 list\n",
    "            \n",
    "            for j in range(base_len - 1 + (1 if reminder else 0)):\n",
    "                # 每個 part 一開始就是 cur\n",
    "                # 只要走 base_len - 1 就可以走到 base_len 的那一個 node\n",
    "                if cur == None:\n",
    "                    break\n",
    "                cur = cur.next\n",
    "            \n",
    "            # 如果 reminder > 0, 代表這一個 part 有分到 extra node\n",
    "            # 分到了就得扣掉一個\n",
    "            reminder -= (1 if reminder else 0)\n",
    "        \n",
    "            if cur:\n",
    "                # 這個 part 最後要指到 null, 還要把 cur 往前推進給下一個 part\n",
    "                cur.next, cur = None, cur.next\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        # 统计链表长度\n",
    "        cnt = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            cnt += 1\n",
    "            cur = cur.next\n",
    "        res = [int(cnt/k) for i in range(k)]\n",
    "        diff = cnt - sum(res)\n",
    "        for i in range(diff):\n",
    "            res[i] += 1\n",
    "        new_res = []\n",
    "\n",
    "        old_head = head\n",
    "        for lens in res:\n",
    "            if lens==0:\n",
    "                new_res.append(None)\n",
    "                continue\n",
    "            cur = old_head\n",
    "            for k in range(lens-1):\n",
    "                cur = cur.next\n",
    "            new_res.append(old_head)\n",
    "            old_head = cur.next\n",
    "            cur.next = None            \n",
    "        return new_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        size_parts = [0]*k\n",
    "        size = 0\n",
    "        ans = [None for i in range(k)]\n",
    "        cur = head\n",
    "        while cur:\n",
    "            size+=1\n",
    "            cur = cur.next\n",
    "        mod = size % k\n",
    "        s = size // k\n",
    "\n",
    "        for i in range(len(size_parts)):\n",
    "            size_parts[i] += s\n",
    "            if mod != 0:\n",
    "                size_parts[i] += 1\n",
    "                mod -= 1\n",
    "\n",
    "        cur = head\n",
    "        for i in range(k):\n",
    "            if cur == None:  \n",
    "                continue\n",
    "            ans[i] = cur\n",
    "            for _ in range(size_parts[i]-1):\n",
    "                cur = cur.next\n",
    "            \n",
    "            temp = cur.next\n",
    "            cur.next = None\n",
    "            cur = temp        \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n",
    "        # 将链表尽可能分成k个部分\n",
    "        # 这k个部分的长度不要超过1\n",
    "        \n",
    "        # 这个数组存储的是这k个链表的头\n",
    "        # headlis = [ListNode() for _ in range(k)]\n",
    "        # curlis = headlis[:]\n",
    "        curn = head\n",
    "        step = 0\n",
    "        while curn:\n",
    "            curn = curn.next\n",
    "            step += 1\n",
    "        \n",
    "        # 总共分成k堆，每一堆基础分为step//k，另外有step%k堆会多一个 \n",
    "        min_heap = step//k \n",
    "        max_heap_num = step%k \n",
    "        # 前max_heap_num个多一个的堆\n",
    "        cur = head\n",
    "        res = []\n",
    "        for i in range(max_heap_num):\n",
    "            res.append(cur)\n",
    "            for _ in range(min_heap):\n",
    "                cur = cur.next\n",
    "            nxt = cur.next\n",
    "            cur.next = None\n",
    "            cur = nxt\n",
    "            \n",
    "        for i in range(k - max_heap_num):\n",
    "            res.append(cur)\n",
    "            for _ in range(min_heap-1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "            if cur:\n",
    "                nxt = cur.next\n",
    "                cur.next = None\n",
    "                cur = nxt\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
